package algorithms.leaning.class11;

import common.bean.TreeNode;
import common.util.MyUtil;

import java.util.LinkedList;

/**
 * 使用先序遍历对二叉树进行序列化和反序列化
 * <p>
 * 先序和后序可以，中序不行
 *
 * @author guichang
 * @date 2021/6/9
 */

@SuppressWarnings("all")
public class Code2_二叉树_序列化_先序遍历 {
    public static void main(String[] args) {
        TreeNode oNode = MyUtil.createTreeNode(1, 2, 3, 4);
        LinkedList<Integer> list = encode(oNode);
        MyUtil.print(list);
        MyUtil.printTreeNode(decode(list));
    }

    /**
     * 序列化
     */
    public static LinkedList<Integer> encode(TreeNode node) {
        LinkedList<Integer> list = new LinkedList<>();
        inEncode(node, list);
        return list;
    }

    private static void inEncode(TreeNode node, LinkedList<Integer> list) {
        if (node == null) {
            list.offer(null);
            return;
        }
        list.offer(node.val);
        inEncode(node.left, list);
        inEncode(node.right, list);
    }

    /**
     * 反序列化
     */
    public static TreeNode decode(LinkedList<Integer> list) {
        return inDecode(list);
    }

    private static TreeNode inDecode(LinkedList<Integer> list) {
        Integer val = list.poll();
        if (val == null) {
            return null;
        }
        TreeNode node = new TreeNode(val);
        node.left = inDecode(list);
        node.right = inDecode(list);
        return node;
    }
}